use crate::stools::random_num;
use std::{
    cell::RefCell,
    collections::{HashMap, VecDeque},
    fmt::{Debug, Display},
    hash::{Hash, Hasher},
    ops::Deref,
    rc::Rc,
};

struct RandomPool<K> {
    key_idx: HashMap<K, usize>,
    idx_key: HashMap<usize, K>,
    size: usize,
}
impl<K: Debug> Display for RandomPool<K> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        for (k, v) in &self.key_idx {
            write!(f, "({:?}:{:?}), ", k, v)?;
        }
        Ok(())
    }
}

impl<K: Clone + Debug + Eq + Hash> RandomPool<K> {
    fn new() -> Self {
        Self {
            key_idx: HashMap::new(),
            idx_key: HashMap::new(),
            size: 0,
        }
    }

    fn insert(&mut self, key: K) -> &mut Self {
        self.idx_key.entry(self.size).or_insert({
            self.size += 1;
            key.clone()
        });
        self.key_idx.entry(key).or_insert(self.size);
        self
    }

    fn delete(&mut self, key: K) -> &mut Self {
        if !self.key_idx.contains_key(&key) || self.size == 0 {
            return self;
        }

        let idx = self.key_idx.get(&key).unwrap();
        self.size -= 1;
        let key_last = self.idx_key.get(&self.size).unwrap().clone();
        self.idx_key.insert(*idx, key_last);
        self.key_idx.remove(&key);
        self.idx_key.remove(&self.size);

        self
    }

    fn random(&self) -> Option<&K> {
        self.idx_key.get(&(random_num(0..self.size)))
    }
}

fn infect(array: &mut Vec<Vec<usize>>, i: usize, j: usize) -> usize {
    if i >= array[0].len() || j >= array.len() || array[i][j] != 1 {
        return 0;
    }
    array[i][j] = 2;
    (i > 0).then(|| infect(array, i - 1, j));
    infect(array, i + 1, j);
    (j > 0).then(|| infect(array, i, j - 1));
    infect(array, i, j + 1);
    return 1;
}

fn print_sea(a: &Vec<Vec<usize>>) {
    println!("====== sea ======");
    for i in 0..a.len() {
        println!("{:?}", a[i]);
    }
}

fn create_sea(size: usize) -> Vec<Vec<usize>> {
    let mut array: Vec<Vec<usize>> = Vec::new();

    for i in 0..size {
        array.push(Vec::new());
        for _ in 0..size {
            array[i].push(random_num(0..2));
        }
    }

    array
}

fn how_many_island() {
    let sz = random_num(1..10);
    let mut sea = create_sea(sz);
    let mut islands = 0usize;

    println!("\n====== how many island ======");
    print_sea(&sea);
    for i in 0..sz {
        for j in 0..sz {
            islands += infect(&mut sea, i, j);
        }
    }
    print_sea(&sea);
    println!("海中有{}个岛屿", islands);
}

fn test_random_pool() {
    let mut random_pool = RandomPool::new();
    let s = ["hello", "world", "rayn", "miller", "有钱", "悠闲", "希望"];
    for c in s {
        random_pool.insert(c);
    }
    println!("\nrandom pool: {}", random_pool);

    print!("随机抽取元素: [");
    for _ in 0..5 {
        print!("{:?}, ", random_pool.random());
    }
    println!("]");

    println!("删除元素:");
    for i in 0..5 {
        random_pool.delete(s[i]);
        println!("{}", random_pool);
    }
}

#[derive(Eq)]
struct ElemLink<T>(Rc<RefCell<T>>);
impl<T: Display> Display for ElemLink<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.0.borrow())?;

        Ok(())
    }
}
impl<T> Hash for ElemLink<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.as_ref().as_ptr().hash(state);
    }
}
impl<T> PartialEq for ElemLink<T> {
    fn eq(&self, other: &ElemLink<T>) -> bool {
        self.as_ref().as_ptr() == other.as_ref().as_ptr()
    }
}
impl<T> Deref for ElemLink<T> {
    type Target = Rc<RefCell<T>>;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}
impl<T> Clone for ElemLink<T> {
    fn clone(&self) -> Self {
        ElemLink(self.0.clone())
    }
}
impl<T: Display> ElemLink<T> {
    fn new(elem: T) -> Self {
        Self(Rc::new(RefCell::new(elem)))
    }
}

struct UnionFindSet<T> {
    elem_map: HashMap<T, ElemLink<T>>,
    father_map: HashMap<ElemLink<T>, ElemLink<T>>,
    size_map: HashMap<ElemLink<T>, usize>,
}
impl<T: Display> Display for UnionFindSet<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "elem_map: ")?;
        for (k, v) in &self.elem_map {
            write!(f, "{{{}: [{}]}}, ", k, v)?;
        }
        writeln!(f, "")?;

        write!(f, "father_map: ")?;
        for (k, v) in &self.father_map {
            write!(f, "{{[{}]: [{}]}}, ", k, v)?;
        }
        writeln!(f, "")?;

        write!(f, "size_map: ")?;
        for (k, v) in &self.size_map {
            write!(f, "{{[{}]: {}}}, ", k, v)?;
        }
        writeln!(f, "")?;

        Ok(())
    }
}
impl<T: Clone + Eq + Hash + Display> UnionFindSet<T> {
    fn new(array: &[T]) -> Self {
        let mut set = Self {
            elem_map: HashMap::new(),
            father_map: HashMap::new(),
            size_map: HashMap::new(),
        };
        for e in array {
            let elink = ElemLink::new(e.clone());
            set.elem_map.insert(e.clone(), elink.clone());
            set.father_map.insert(elink.clone(), elink.clone());
            set.size_map.insert(elink.clone(), 1);
        }

        set
    }

    fn find_top(&mut self, a: &T) -> Option<ElemLink<T>> {
        if !self.elem_map.contains_key(a) {
            return None;
        }

        let mut stack: Vec<ElemLink<T>> = Vec::new();
        let mut link = self.elem_map.get(a).unwrap();
        while link != self.father_map.get(link).unwrap() {
            stack.push(link.clone());
            link = self.father_map.get(link).unwrap();
        }

        let father = link.clone();
        while let Some(link) = stack.pop() {
            self.father_map.insert(link.clone(), father.clone());
        }

        Some(father.clone())
    }

    fn union(&mut self, a: &T, b: &T) -> &mut Self {
        let atop = self.find_top(a);
        let btop = self.find_top(b);
        if atop.is_none() || btop.is_none() {
            return self;
        }
        let atop = atop.unwrap();
        let btop = btop.unwrap();
        if atop != btop {
            let big = if self.size_map.get(&atop) > self.size_map.get(&btop) {
                atop.clone()
            } else {
                btop.clone()
            };
            let small = if big == atop {
                btop.clone()
            } else {
                atop.clone()
            };
            self.father_map.insert(small.clone(), big.clone());
            self.size_map.insert(
                big,
                self.size_map.get(&atop).unwrap() + self.size_map.get(&btop).unwrap(),
            );
            self.size_map.remove(&small);
        }
        self
    }

    fn is_same_set(&mut self, a: &T, b: &T) -> bool {
        let atop = self.find_top(a);
        let btop = self.find_top(b);
        if atop.is_none() || btop.is_none() {
            return false;
        }
        if atop == btop {
            true
        } else {
            false
        }
    }
}

fn test_unionfindset() {
    println!("\n======= 并查集 ==========");
    let mut ufset = UnionFindSet::new(&['a', 'b', 'c', 'd', 'a', 'f']);
    println!("{}", ufset);

    println!("a和b是同一集合：{}", ufset.is_same_set(&'a', &'b'));
    println!("合并a、b：{}", ufset.union(&'a', &'b'));
    println!("a和b是同一集合：{}", ufset.is_same_set(&'a', &'b'));
    println!("合并a、c：{}", ufset.union(&'a', &'c'));
    println!("合并a、d：{}", ufset.union(&'a', &'d'));
    println!("a和c是同一集合：{}", ufset.is_same_set(&'a', &'c'));
    println!("a和d是同一集合：{}", ufset.is_same_set(&'a', &'d'));
    println!("a和1是同一集合：{}", ufset.is_same_set(&'a', &'1'));
}

#[derive(Clone, Eq, PartialEq, Hash)]
struct Pos(usize, usize);
impl Display for Pos {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "({}, {})", self.0, self.1)?;
        Ok(())
    }
}

fn get_next_array(s: &str) -> Vec<i32> {
    let s: Vec<u8> = Vec::from(s);
    let mut next: Vec<i32> = vec![0; s.len()];
    let mut idx: usize = 2;
    next[0] = -1;
    next[1] = 0;
    let mut should_same: usize = next[idx - 1] as usize;

    while idx < s.len() {
        if s[idx - 1] == s[should_same] {
            should_same += 1;
            next[idx] = should_same as i32;
            idx += 1;
        } else if should_same == 0 {
            next[idx] = 0;
            idx += 1;
        } else {
            should_same = next[should_same] as usize;
        }
    }

    next
}

fn kmp(s1: &str, s2: &str) -> Option<usize> {
    let next = get_next_array(s2);
    let s1 = Vec::from(s1);
    let s2 = Vec::from(s2);
    let mut i1: usize = 0;
    let mut i2: usize = 0;

    while i1 < s1.len() && i2 < s2.len() {
        if s1[i1] == s2[i2] {
            i1 += 1;
            i2 += 1;
        } else if i2 > 0 {
            i2 = next[i2] as usize;
        } else {
            i1 += 1;
        }
    }

    if i2 == s2.len() {
        Some((i1 - i2) as usize)
    } else {
        None
    }
}

fn expand_str(s: &str) -> Vec<char> {
    let mut v: Vec<char> = vec!['a'; 2 * s.len() + 1];
    let s: Vec<u8> = Vec::from(s);
    for (i, c) in v.iter_mut().enumerate() {
        *c = if (i & 1) == 0 { '#' } else { s[i / 2] as char }
    }

    v
}

fn manacher(s: &str) -> Option<usize> {
    if s.len() == 0 {
        return None;
    }
    let s = expand_str(s);
    let mut radis: usize = 0;
    let mut r: Vec<usize> = vec![1; s.len()];
    let mut center: usize = 0;
    let mut max_len: usize = 0;

    for i in 0..s.len() {
        r[i] = if i < radis {
            r[2 * center - i].min(radis - i)
        } else {
            1
        };
        while i + r[i] < s.len() && i >= r[i] {
            if s[i - r[i]] == s[i + r[i]] {
                r[i] += 1;
            } else {
                break;
            }
        }
        if i + r[i] > radis {
            radis = i + r[i];
            center = i;
        }
        max_len = max_len.max(r[i]);
    }

    Some(max_len - 1)
}

fn slide_win_maxmin(nums: &[i32], width: usize) -> Vec<i32> {
    let mut decrease: VecDeque<usize> = VecDeque::new(); // 单调递减队列(保存nums的idx)
    decrease.push_front(0);
    let mut max: Vec<i32> = Vec::new();

    for i in 1..nums.len() {
        while let Some(idx) = decrease.back() {
            if nums[*idx] > nums[i] {
                break;
            }

            decrease.pop_back();
        }
        decrease.push_back(i);

        if let Some(&idx) = decrease.front() {
            if i >= width && idx == (i - width) {
                decrease.pop_front();
            }
            if i >= width - 1 {
                max.push(nums[idx]);
            }
        }
    }

    max
}

#[derive(Debug)]
struct BiggerNum {
    idx: usize,
    left: Option<usize>,
    right: Option<usize>,
}
impl BiggerNum {
    fn new(idx: usize) -> Self {
        Self {
            idx,
            left: None,
            right: None,
        }
    }
}

// 分别找到nums[idx]左右最近的比它大的数
fn nearest_bigger_num(nums: &[i32]) -> Vec<BiggerNum> {
    let mut bigger_array: Vec<BiggerNum> = vec![];
    // 每个数的坐标，如果有相同大小的数，就放到 vec 中
    let mut decrease_stack: Vec<usize> = vec![];

    for (i, &num) in nums.iter().enumerate() {
        while let Some(&idx) = decrease_stack.last() {
            if nums[idx] < num {
                let mut bigger = BiggerNum::new(decrease_stack.pop().unwrap());
                bigger.right = Some(i);
                decrease_stack.last().map(|&i| bigger.left = Some(i));
                bigger_array.push(bigger);
            } else {
                decrease_stack.push(i);
                break;
            }
        }
        if decrease_stack.is_empty() {
            decrease_stack.push(i);
        }
    }

    // decrease_stack还有数据
    while let Some(idx) = decrease_stack.pop() {
        let mut bigger = BiggerNum::new(idx);
        bigger.right = None;
        decrease_stack.last().map(|&i| bigger.left = Some(i));
        bigger_array.push(bigger);
    }

    bigger_array
}

#[derive(Debug)]
struct Emplyee {
    happy: u32,
    next: Vec<Box<Emplyee>>,
}
impl Emplyee {
    fn new(happy: u32) -> Self {
        Self {
            happy,
            next: vec![],
        }
    }
}

struct HappyInfo {
    nocome_happy: u32,
    come_happy: u32,
}

fn max_happy_recursion(e: &Emplyee) -> HappyInfo {
    if e.next.is_empty() {
        return HappyInfo {
            nocome_happy: 0,
            come_happy: e.happy,
        };
    }

    let mut come = e.happy;
    let mut no_come = 0u32;
    for n in &e.next {
        let info = max_happy_recursion(n);
        come += info.nocome_happy;
        no_come += info.come_happy.max(info.nocome_happy);
    }

    HappyInfo {
        nocome_happy: come,
        come_happy: no_come,
    }
}

fn max_happy(e: &Emplyee) -> u32 {
    let info = max_happy_recursion(e);
    info.come_happy.max(info.nocome_happy)
}

///公司架构：level1 -> l2 -> l3 -> l4
fn create_company() -> Emplyee {
    // 1层1个人
    let mut l1 = Emplyee::new(random_num(10..100));
    // 每个1层管2人
    for _l2 in 0..2 {
        l1.next.push(Box::new(Emplyee::new(random_num(10..100))));
    }
    // 每个2层管3人
    for _l3 in 0..3 {
        for l2 in &mut l1.next {
            l2.next.push(Box::new(Emplyee::new(random_num(10..100))));
        }
    }
    // 每个3层管2人
    for _l4 in 0..2 {
        for l2 in &mut l1.next {
            for l3 in &mut l2.next {
                l3.next.push(Box::new(Emplyee::new(random_num(10..100))));
            }
        }
    }

    l1
}

/// 统计40亿个数出现频率最多的数，1G内存
/// 思路：分流
/// 1G内存保守可以创建64M大小的hash表，Hash<i32, u32>：i32数字出现的次数
/// 将 2^32 / 64M = 2^32/(2^6 * 2^20) =  2^6 = 64 个区域
/// 把数字放到文件中
/// ```
/// for num in 40亿个数 {
///     file[hash(num)%64].input(num);
/// }
/// ```
/// 在文件 file[i] 中，统计词频
/// ```
/// for num in file[i] {
///     hash.entry(num).and_modify(|num| num += 1).or_insert(1)
/// }
/// ```
fn find_most_freq_num() {}

/// uint32_t的范围是[0, 2^32-1]，有40亿个数，3Kb内存，找出所有未出现过的数
/// 思路1)：用域频，将[0, 2^32)分成x区域，每个区域必须有2^32/x个数字，不满说明这个区域缺少数字
/// 从3KB中可以建立2^9个元素的域频数组i32 freq[]，那么就将 [0, 2^32) 分成 2^9 份，每份应该有 2^23 个数
/// ```
/// for num in nums {
///     freq[num/(2^23)] += 1;
/// }
///
/// for i in freq.len() {
///     if freq[i] < 2^29 {break;} // 这个freq[i]中有未出现过的数
/// }
/// ```
/// freq[i]再以2^9为区域，分组，直到找到未出现的数字
///
/// 找到出现2次的数
/// 使用位图，用2bit表示一个数出现的次数；对于 2^32 个数，需要 2*2^32 / 8 = 2^29 = 512MB 的空间；
fn find_disappear_num() {}

/// 40亿个数，找到中位数
/// 思路：范围统计（域频数组freq[]），sum(freq[0..i]) >= 20亿时，这个中位数就出现在freq[i]中
fn find_middle_num() {}

/// 10G文件，内部i32数据，无序；通过 5G 内存变为有序
/// 思路1）：用最小堆和elem(数字,次数)来实现
/// sizeof(数字，次数) = 8，heap(elem)中每个元素假设占16byte，5G/16 = 2^27，5G可以建立2^27元素的最小堆
/// 第一堆装入[0, 2^27)的数据，形成[(0, 3), (1, 100), (2, 13), ...]，然后将第一堆依次放入文件中
/// 第2堆装入[2^27, 2*2^27)，再将第2堆放入文件中
///
/// 思路2）：最大堆和elem(数字，次数)
/// 将数字装入堆，因为当最大堆满时，大于堆的数字不会入堆，所以第1堆自然为[(2^27-1, 100), (2^27-2, 99),...(0,100)]，
/// 令y=堆顶值；将第1堆写入文件，第2堆只有比y大的入堆，依次进行
fn sort_10g_file() {}

/// bool翻转
fn flip(a: bool) -> bool {
    !a
}

/// 数是正数
fn positive(num: i32) -> bool {
    flip((num >> 31) == 1)
}

/// 给定2个i32数字a和b，返回大数，不用比较判断
/// 能找到互斥条件：dif_sign/same_sign, returna/returnb
/// 会用flip找到互斥条件 flip(dif_sign)
/// 互斥条件才能用+表示或关系
fn get_bigger(a: i32, b: i32) -> i32 {
    let c: i32 = a - b;
    let pa = positive(a);
    let pb = positive(b);
    let pc = positive(c);
    let dif_sign = pa ^ pb;
    let same_sign = flip(dif_sign);
    let return_a = (dif_sign && pa) || (same_sign && pc);
    let return_b = flip(return_a);

    return_a as i32 * a + return_b as i32 * b
}

/// 判断一个32位正数是不是2的幂、4的幂
/// 2的幂的数，只有一个bit是1，方法1：可以取数的最右1位 == 原数；方法2：num & (num - 1) == 0
/// 4的幂：只有一个bit是1，并且 num && 0xaaaaaaaa != 0
fn is_2_pow(a: u32) -> bool {
    // 最右的1
    let most_right_one = a & (!a + 1);
    let is_2_pow1 = most_right_one == a;
    let is_2_pow2 = ((a - 1) & a) == 0;
    assert_eq!(is_2_pow1, is_2_pow2);

    is_2_pow1
}

fn is_4_pow(a: u32) -> bool {
    is_2_pow(a) && (a & 0xaaaaaaaa != 0)
}

/// 有符号的32位整数a和b，不使用算术运算符，实现a和b的+-*/
/// 如果给定的a、b执行运算结果会溢出，函数不必对此负责，除此之外保证计算过程不发生溢出
/// 加法
/// a ^ b 是bit的不进位加法，a & b 是会出现进位的那些位，(a&b)<<1是出现的进位
fn nums_add(a: i32, b: i32) -> i32 {
    let mut xor = a ^ b;
    let mut carry = (a & b) << 1;
    let mut tmp;
    // 结果就是 a不进位结果 + b进位信息 = (a^b) + ((a&b)<<1)，直到没有进位
    while carry != 0 {
        tmp = xor ^ carry;
        carry = (xor & carry) << 1;
        xor = tmp;
    }

    xor
}

fn negnum(a: i32) -> i32 {
    nums_add(!a, 1)
}

/// 减法就是a + b的相反数(取反+1)
fn nums_minus(a: i32, b: i32) -> i32 {
    nums_add(a, negnum(b))
}

/// 根据b的1所在i位，sum += (a<<i)
fn nums_multiply(mut a: i32, mut b: i32) -> i32 {
    let mut multiply = 0;

    while b != 0 {
        ((b & 1) == 1).then(|| multiply = nums_add(multiply, a));
        b >>= 1;
        a <<= 1;
    }

    multiply
}

/// 除法 a/b
/// x = (b << i)，同时不超过a，a - x 是可以减的
fn nums_divide(mut a: i32, b: i32) -> (i32, i32) {
    let mut div = 0;

    while b < a {
        div = nums_add(div, 1);
        a = nums_minus(a, b);
    }
    (div, a)
}

pub fn hash_main() {
    test_random_pool();
    how_many_island();
    test_unionfindset();
    println!("{:?}", kmp("abbsabbtcabbsabbe", "abbsabbtcabbsabbw"));
    println!("{:?}", kmp("abbsabbtcabbsabbe", "tcabbsa"));
    println!("{:?}", kmp("abbsabbtcabbsabbe", "abbsa"));
    println!("{:?}", manacher("abcbdkskdbcba"));

    println!("\n================== 滑动窗口最大值 ================");
    let nums = [3, 2, 1, 1, 4, 5, 2, 4, 7, 5, 8, 2, 1, 5];
    let mut width = 4;
    println!("数组：{:?}，窗口宽度：{}", nums, width);
    println!("最大值数组：{:?}", slide_win_maxmin(&nums, width));
    width = 3;
    println!("数组：{:?}，窗口宽度：{}", nums, width);
    println!("最大值数组：{:?}", slide_win_maxmin(&nums, width));

    println!("\n================== 邻近最大值 ================");
    let nums = [5, 4, 6, 7, 2, 3, 0, 1];
    println!("数组{:?}的邻近最大值：", nums);
    let v = nearest_bigger_num(&nums);
    for n in v {
        println!("{:?}", n);
    }

    println!("\n================== 快乐最大值 ================");
    let company = create_company();
    println!("公司架构：{:#?}", company);
    println!("最大快乐值：{}", max_happy(&company));

    println!("\n================== 数据的四则运算 ================");
    println!("{} + {} = {}", 13, 7, nums_add(13, 7));
    println!("{} * {} = {}", 14, 9, nums_multiply(14, 9));
    println!("{} / {} = {:?}", -21, 9, nums_divide(-21, 10));
}
